10367. Заражение

Фермер Джон и его коллеги работают без остановки, пытаясь сдержать распространение опасной болезни крупного рогатого скота COWVID-19 на своих фермах.

Всего под наблюдением находится n ферм, пронумерованных от 1 до n. Фермы соединены n – 1 дорогой, причём от фермы 1 можно добраться до любой другой по некоторой последовательности дорог.

К сожалению, корова на ферме 1 только что получила положительный результат на COWVID-19. Пока что ни одна другая корова – ни на этой, ни на остальных фермах – не заражена. Однако, учитывая чрезвычайно высокую заразность болезни, фермер Джон понимает, что в каждый последующий день может произойти одно из двух событий:

· на одной из ферм происходит суперраспространение, в результате чего количество заражённых коров на этой ферме удваивается;

· одна заражённая корова переходит по дороге с одной фермы на соседнюю.

Фермер Джон обеспокоен тем, насколько быстро может распространиться вспышка болезни. Помогите ему определить минимальное количество дней, необходимое для того, чтобы на каждой ферме оказалась хотя бы одна заражённая корова.

Вход. Первая строка содержит одно целое число n (1 ≤ n ≤ 10⁵). Каждая из следующих n – 1 строк содержит два целых числа a и b, обозначающих дорогу между фермами a и b (1 ≤ a, b ≤ n).

Выход. Выведите минимальное количество дней, через которое вспышка болезни может достигнуть каждой фермы.

Пример входа	Пример выхода
4 1 2 1 3 1 4	5

РЕШЕНИЕ

графы

Анализ алгоритма

Чтобы заразить все фермы, необходимо выполнить два типа действий:

· Перемещения. Нужно отправить ровно n − 1 корову по дорогам (каждая дорога используется хотя бы раз). Следовательно, минимум n − 1 день потребуется только на перемещения коров между фермами.

· Удвоения. Поскольку на ферме изначально заражена лишь одна корова, нам сначала необходимо “вырастить” нужное количество коров, выполняя операции удвоения.

Заметим, что удвоения и переходы могут происходить в разных местах дерева после заражения.

Пусть на ферму v пришла одна больная корова. Если ферма v имеет x детей в дереве, то она должна отправить заражённых коров на x соседей, поэтому ей нужно иметь как минимум x коров.

Сначала на ферме v имеется 1 корова. Совершаем удвоения: 1 → 2 → 4 → 8 …. Минимальное количество удвоений, чтобы получить не менее x коров, равно .

Таким образом, минимальное количество дней, необходимое для распространения болезни по всем фермам, равно

(n – 1) +

По условию задачи достаточно, чтобы в какой-то момент времени на каждой ферме побывала хотя бы одна заражённая корова. В условии не сказано, что после заражения всех ферм на каждой ферме должна остаться хотя бы одна зараженная корова.

Реализация алгоритма

Дерево храним в виде списка смежности g.

vector<vector<int>> g;

Функция dfs выполняет обход в глубину, начиная с вершины v и возвращает количество дней, необходимых для удвоения заражённых коров во всех вершинах поддерева с корнем в v. Предком вершины v является par.

int dfs(int v, int par = 0)

{

int ans = 0;

for (int to : g[v])

if (to != par)

ans += dfs(to, v);

return ans + ceill(log2(g[v].size()));

}

Основная часть программы. Читаем входные данные. Строим граф.

scanf("%d", &n);

g.resize(n + 1);

for (i = 0; i < n - 1; i++)

{

scanf("%d %d", &a, &b);

g[a].push_back(b);

g[b].push_back(a);

}

Запускаем поиск в глубину из вершины 1 и вычисляем минимальное количество дней, необходимое для заражения всех ферм. Ответ сохраняем в переменной res.

res = dfs(1) + n - 1;

Выводим ответ.

printf("%d\n", res);